Intermediate System To Intermediate System (IS-IS) is a link state routing protocol that is described in ISO 10589, Second Edition, which was published on 2002 Nov. 15, and republished in RFC 1142. The IS-IS protocol natively operates at the Open Systems Interconnection (OSI) model network layer. IS-IS is an interior gateway protocol typically used for routing within an administrative domain or network, as opposed to an exterior gateway protocol typically used for routing between autonomous systems.
According to IS-IS, each IS-IS router is to operate as an originating router and is to transmit link state advertisements having state information throughout the IS-IS network of routers. Commonly, the link state advertisements may be Link State Protocol Data Units (LSPs) having Type-Length-Value (TLV) elements that each includes link state information. Each LSP may identify the originating router that generated it and may identify all the other routers to which the originating router is directly connected. Each receiving IS-IS router is to use the link state information to build and maintain a database representing the connectivity of the network (e.g., a link state database), and is to forward a copy of the link state advertisements to each of their respective neighboring routers. Each of the receiving routers is also to calculate and store a shortest path to each of the destinations (e.g., in a routing table). The routers may use these shortest paths to route or forward data or traffic (e.g., packets or datagrams).
FIG. 1 is a block diagram of an example IS-IS network 100. The network includes an originating IS-IS router 101 and a receiving IS-IS router 107. The originating IS-IS router has an IS-IS routing protocol module 102 that includes a route distribution module 103. The originating IS-IS router also has a routing information base 104. Periodically, when connectivity changes occur, etc., the route distribution module 103 may access the routing information base 104 and distribute link state advertisements (e.g., LSPs) to the receiving IS-IS router 107. As shown, an LSP 106 having a TLV-A element 114A and a TLV-B element 114B may be transmitted to the receiving IS-IS router over a link 105. Each of the TLV-A and TLV-B elements may include link state information. The receiving IS-IS router has an IS-IS routing protocol module 108 that includes a shortest path first (SPF) computation module 109 and a routing information base update module 110. The receiving IS-IS router also has a routing information base 111, which includes a link state database 113 and a routing table 112. When the LSP 106 is received, the routing information base update module may store link state or connectivity represented in the LSP in the link state database. The shortest path computation module may compute a shortest path based on the link state or connectivity. The routing information base update module may store the computed shortest paths in the routing table.
Periodically, when connectivity changes occur, etc., the originating router 101 is to transmit a refresh or update link state advertisement (e.g., an LSP). According to IS-IS each link state advertisement or LSP is to include a sequence number. The originating router is to increase the sequence number each time a newer version of the link state advertisement or LSP is generated. The receiving router is to preserve the highest sequence number received. When the receiving router receives the refresh or update LSP it is to look up the preserved highest previously received sequence number. If the sequence number of the refresh or update LSP is greater than the preserved sequence number, then the refresh or update LSP is considered newer and relevant. Then, the receiving router is to use the refresh or update LSP to refresh or update the database representing the connectivity of the network (e.g., the link state database). Moreover, the refreshed or updated connectivity is to be used to calculate a new potentially different shortest path to all of the destinations in the network. These refreshed or updated shortest paths are to be stored (e.g., in a routing table) and used to route or forward data or traffic.
FIG. 2 is an illustration showing that two or more refresh or update link state advertisements (e.g., LSPs) 206R1, 206R2 need to be transmitted when additional information 217 causes the total amount of link state information to exceed a fixed maximum message size 216. In IS-IS the link state advertisements (e.g., LSPs) have a fixed maximum message size 216. This fixed maximum message size is sometimes referred to as the maximum transfer unit (MTU). As shown on the left-hand side of the illustration, a previously transmitted LSP 206P is shown to have the maximum message size. As shown, both a TLV-A element 214A and a TLV-B element 214B have sizes such that they are both able to fit within the fixed maximum message size and be accommodated within the single previously transmitted LSP 206P.
However, in some cases, after transmission of the previously transmitted LSP 206P, the additional information 217 may need to be included in one or more of the TLV elements (in the illustrated case in the TLV-B element). By way of example, the additional information may include additional link state information for additional links or connections added to the IS-IS network and/or additional information pertaining to existing links (e.g., bandwidth information, level of service information, other traffic engineering information, etc.). In some cases, this additional information may cause the total amount of information to exceed the fixed maximum message size. As shown on the right hand side of the illustration, the TLV-A element 214A and a changed TLV-B′ element 214B′ having the additional information 217 no longer fit with in the fixed maximum message size of a refresh/update LSP 206R. This is designated by the “X” through the LSP 206R. In such cases, some of the link state information and/or one or more of the TLV elements from previously transmitted LSPP may need to be relocated to an additional link state advertisement or LSP. In the illustration, a first refresh or update LSP 206R1 having the TLV-A element 214A as well as a second refresh or update LSP element 206R2 having the TLV-B′ element 214B′ with the additional information 217 are transmitted to the network.
In addition to having a fixed maximum message size, IS-IS presently lacks an underlying datagram fragmentation capability. By contrast, OSPF run on the Internet Protocol (IP) level. As a result, OSPF is able to take advantage of the capability of the underlying TCP/IP stack to perform datagram fragmentation. In datagram fragmentation, the underlying transport layer may fragment or divide a larger packet into two or more smaller packets that may be transmitted, and then on the receiving end the counterpart transport layer may reassemble the two or more smaller packets to re-generate the larger packet and provide the re-generated larger packet to the receiving OSPF protocol. The OSPF protocol does not need to be concerned with the datagram fragmentation process. Consequently, in OSPF additional information may be added to a packet, and the packet may be allowed to grow in size, without the limitation of a fixed maximum message size. In contrast, IS-IS runs directly on the datalink layer and presently lacks an underlying datagram fragmentation mechanism.